#include "code.h"
#include <numeric>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <ctime>
#define P 10000
#define random() rand()%(P)/(float)(P)
#define randomint(a,b) (rand() % (b-a))+ a; 

double d_max(code *DNA, city *C, int _l);
double *cdf(double *eval, int _l);
int bisection_search(double *cdf, double eta, int _start, int _end);
int roulett(double *cdf, int _l);
int roulett(code *_DNA, city *C, int _l, double _max);
int two_championship(code *_DNA, city *C, int _l);
void copy(code *_DNA, code *_nDNA, city *C, int _p, int _l);
int find(int *_arr, int _p, int _l);
void order_cross(int* _arr1, int* _arr2, int* _arr3, int* _arr4, int _l);
void crossover(code *_DNA, code *_nDNA, city *C, int _p, int _l, int t, double _max);
void replace(int* _arr1, int* _arr2, int _l);
void mutation(code *_DNA, code *_nDNA, city *C, int _p, int _l, double _max);
void reproduce(code *_DNA, code *_nDNA, city *C, int _l , double Pr , double Pc , double Pm, double _max);



double d_max(code *DNA, city *C, int _l){
  int leng=DNA[0].get_length();
  double max=0;
  for (int i=0; i<_l ; i++){
    double dis=DNA[i].total_dis(C,leng);
    if (dis > max)
      max = dis;
  }
  return max;
}

double *cdf(double *eval, int _l){
  double sum=std::accumulate(eval, eval + _l, 0);
  double *table = new double[_l];
  for (int i=0; i<_l; i++)
    table[i]=std::accumulate(eval, eval + i + 1, 0)/sum;
  return table;
}

int bisection_search(double *cdf, double eta, int _start, int _end){
  if (eta < cdf[_start])
    return _start;
  int k = (_start + _end)/2;
  if (eta > cdf[k]){
    if (eta <= cdf[k+1])
      return k+1;
    else
      return bisection_search(cdf, eta, k+1 , _end);
  }
  else
    return bisection_search(cdf, eta , _start, k);
}

int roulett(double *cdf, int _l){
  double y=random();
  int x=bisection_search(cdf,y,0,_l);
  return x;
}

int roulett(code *_DNA,city *C, int _l, double _max){
   int leng=_DNA[0].get_length();
   double *Eval=new double[_l];
   for (int i=0; i<_l ; i++)
     Eval[i]=_DNA[i].fitness(C,leng,_max);
   double* CDF=cdf(Eval,_l);
   int t= roulett(CDF,_l);
   return t;
}



void copy(code *_DNA, code *_nDNA, city *C, int _p, int _l){
  int leng=_DNA[0].get_length();
  int p=two_championship(_DNA,C,_l);
  int *arr=_DNA[p].get_array();
  code D(arr,leng);
  _nDNA[_p]=D;
}

int find(int *_arr, int _p, int _l){
  int t=0;
  for (int i=0; i<_l ; i++){
    if (_arr[i] == _p){
      t=1;
      break;
    }
  }
  if (t==0)
    return 0;
  else
    return 1;
}


void order_cross(int* _arr1, int* _arr2, int* _arr3, int* _arr4, int _l){
  int p=randomint(0,_l);
  int q=randomint(0,_l);
  if (p>q){
    int tmp = p;
    p = q;
    q = tmp;
  }
  int n=q-p+1;
  int* tmp1 = new int[n];
  int* tmp2 = new int[_l-n];
  for (int i=0; i<n ; i++)
    tmp1[i]=_arr1[p+i];
  int k=0;
  for (int i=0; i<_l ; i++){
    if(find(tmp1,_arr2[i],n)==0){
      tmp2[k]=_arr2[i];
      k++;
    }
  }
  k=0;
  for (int i=0; i<_l ; i++){
    if (i>=p && i<=q)
      _arr3[i]=_arr1[i];
    else{
      _arr3[i]=tmp2[k];
      k++;
    }
  }
  for (int i=0; i<n ; i++)
    tmp1[i]=_arr2[p+i];
  k=0;
  for (int i=0; i<_l ; i++){
    if(find(tmp1,_arr1[i],n)==0){
      tmp2[k]=_arr1[i];
      k++;
    }
  }
  k=0;
  for (int i=0; i<_l ; i++){
    if (i>=p && i<=q)
      _arr4[i]=_arr2[i];
    else{
      _arr4[i]=tmp2[k];
      k++;
    }
  }
  delete [] tmp1;
  delete [] tmp2;
}



void crossover(code *_DNA, code *_nDNA, city *C, int _p, int _l, int t){
  int leng=_DNA[0].get_length();
  int p1=two_championship(_DNA,C,_l);
  int p2=two_championship(_DNA,C,_l);
  int* arr1=_DNA[p1].get_array();
  int* arr2=_DNA[p2].get_array();
  int* arr3= new int[leng];
  int* arr4= new int[leng];
  order_cross(arr1,arr2,arr3,arr4,leng);
  code D1(arr3,leng);
  code D2(arr4,leng);
  _nDNA[_p]=D1;
  if (t==2)
    _nDNA[_p+1]=D2;
  
}

void replace(int* _arr1, int* _arr2, int _l){
  int p=randomint(0,_l);
  int q=randomint(0,_l);
  for (int i=0 ; i<_l ; i++){
    if (i == p)
      _arr2[i]=_arr1[q];
    else if (i == q)
      _arr2[i]=_arr1[p];
    else
      _arr2[i]=_arr1[i];
  }
}


void mutation(code *_DNA, code *_nDNA, city *C, int _p, int _l){
  int leng=_DNA[0].get_length();
  int p=two_championship(_DNA,C,_l);
  int* arr1=_DNA[p].get_array();
  int* arr2= new int[leng];
  replace(arr1,arr2,leng);
  code D(arr2,leng);
  _nDNA[_p]=D;
}

void reproduce(code *_DNA, code *_nDNA, city *C, int _l , double Pr , double Pc , double Pm){
  int Nr = (int)(_l*Pr);
  int Nc = (int)(_l*Pc);
  int Nm = _l - Nr - Nc;
  int k=0;
  while (k<Nr){
    copy(_DNA,_nDNA,C,k,_l);
    k++;
  }
  while (k<Nr+Nc){
    if (k+1 == Nr+Nc)
      crossover(_DNA,_nDNA,C,k,_l,1);
    else
      crossover(_DNA,_nDNA,C,k,_l,2);
    k++;
  }
  while (k<_l){
    mutation(_DNA,_nDNA,C,k,_l);
    k++;
  } 
}

int two_championship(code *_DNA, city *C, int _l){
  int leng=_DNA[0].get_length();
  int p=randomint(0,_l);
  int q=randomint(0,_l);
  if (_DNA[p].total_dis(C,leng) >= _DNA[q].total_dis(C,leng))
    return q;
  else
    return p;
}
